public class Test1 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0, n = nums.length;
        for (int num : nums) sum += num;
        int halfSum = (sum + target) / 2;
        if (halfSum < 0 || sum < target || (sum + target) % 2 != 0) return 0;
        int[][] dp = new int[n + 1][halfSum + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= halfSum; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) dp[i][j] += dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][halfSum];
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        int[] arr = {1,1,1,1,1};
        test1.findTargetSumWays(arr,3);
        System.out.println(666);
    }
}
